GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Fundierte Menge</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Fundierte Menge</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">In der <a href="Mathematik" title="Mathematik">Mathematik</a> ist eine fundierte Menge (auch wohlfundierte Menge, fundierte Ordnung, terminierende Ordnung, noethersche Ordnung) eine <a href="Halbordnung" class="mw-redirect" title="Halbordnung">halbgeordnete Menge</a>, die keine unendlichen echt absteigenden Ketten enthält. Äquivalent dazu heißt eine halbgeordnete Menge fundiert, wenn jede nichtleere <a href="Teilmenge" title="Teilmenge">Teilmenge</a> mindestens ein <a href="Minimales_Element" class="mw-redirect" title="Minimales Element">minimales Element</a> enthält.

Alle <a href="Wohlgeordnete_Menge" class="mw-redirect" title="Wohlgeordnete Menge">wohlgeordneten Mengen</a> sind fundiert, weil in einer wohlgeordneten Menge jede nichtleere Teilmenge ein <a href="Kleinstes_Element" class="mw-redirect" title="Kleinstes Element">kleinstes Element</a> haben muss und das kleinste Element einer Menge immer auch minimal ist. Anders als wohlgeordnete Mengen brauchen fundierte Mengen nicht <a href="Totalordnung" class="mw-redirect" title="Totalordnung">totalgeordnet</a> zu sein. Alle total geordneten fundierten Mengen sind wohlgeordnet.

<div class="mw-heading mw-heading2"><h2 id="Noethersche_Induktion">Noethersche Induktion</h2></div>

Fundierte Mengen erlauben die Anwendung der noetherschen Induktion, einer Version der <a href="Transfinite_Induktion" title="Transfinite Induktion">transfiniten Induktion</a>: Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> eine Eigenschaft von Elementen einer unter einer Ordnungsrelation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \leq }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \leq }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/440568a09c3bfdf0e1278bfa79eb137c04e94035.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \leq }" loading="lazy"> fundierten Menge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> und sei die folgende Aussage wahr:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> ein Element von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> ist und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(y)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/871e50f93f66412cc7052e6c158fda0bef991033.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.71ex; height:2.843ex;" alt="{\displaystyle P(y)}" loading="lazy"> für alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y<x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y<x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4052851a7a0fd170365775f6fc8ad079d274ee55.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.584ex; height:2.176ex;" alt="{\displaystyle y<x}" loading="lazy"> wahr ist, dann ist auch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/89833156eff2c51bfb8750db3306a0544ce34e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.884ex; height:2.843ex;" alt="{\displaystyle P(x)}" loading="lazy"> wahr.</dd></dl></dd></dl>

Dann ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/89833156eff2c51bfb8750db3306a0544ce34e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.884ex; height:2.843ex;" alt="{\displaystyle P(x)}" loading="lazy"> wahr für alle Elemente <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Verwendung_in_der_Informatik">Verwendung in der Informatik</h2></div>

Siehe auch: <a href="Termersetzungssystem#Terminierung" title="Termersetzungssystem">Termersetzungssystem#Terminierung</a>

<a href="Terminiertheit" title="Terminiertheit">Terminiertheit</a> ist ein zentrales Konzept in der theoretischen Informatik. Obige Begriffe werden dazu von Ordnungen auf homogene Relationen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\rightarrow b\in A\times A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\rightarrow b\in A\times A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/978170275242657b37417de9b8ccfbe15a510e11.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:15.009ex; height:2.176ex;" alt="{\displaystyle a\rightarrow b\in A\times A}" loading="lazy"> abgeschwächt, wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\rightarrow b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\rightarrow b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/390afdb0d8e933dbc4eee8022d8c91b2015f0522.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.841ex; height:2.176ex;" alt="{\displaystyle a\rightarrow b}" loading="lazy"> etwa den Schritt einer Berechnung repräsentiert. In diesem Zusammenhang ist ein Element <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> einer Teilmenge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B\subseteq A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B\subseteq A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fb8124cb68686ede7083aa2a5a821f262eb62954.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.606ex; height:2.343ex;" alt="{\displaystyle B\subseteq A}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rightarrow }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/53e574cc3aa5b4bf5f3f5906caf121a378eef08b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \rightarrow }" loading="lazy">-minimal, wenn für alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/27bcc9b2afb295d4234bc294860cd0c63bcad2ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.913ex; height:2.176ex;" alt="{\displaystyle x\in A}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\rightarrow x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\rightarrow x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/14ffafdaca35fc902f986715a59737e0381e35f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.984ex; height:1.843ex;" alt="{\displaystyle m\rightarrow x}" loading="lazy"> folgt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\notin B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\notin B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8049ece14bde66bd5b0a3636195d0f33b511bd51.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.934ex; height:2.676ex;" alt="{\displaystyle x\notin B}" loading="lazy">.<a href="#cite_note-1">[1]</a> Neben der Terminiertheit von Algorithmen können vermittels der Noetherschen Induktion dann deren Eigenschaften nachgewiesen werden.

<div class="mw-heading mw-heading2"><h2 id="Beispiele">Beispiele</h2></div>

Die <a href="Ganze_Zahlen" class="mw-redirect" title="Ganze Zahlen">ganzen Zahlen</a>, die <a href="Rationale_Zahlen" class="mw-redirect" title="Rationale Zahlen">rationalen Zahlen</a> und die <a href="Reelle_Zahlen" class="mw-redirect" title="Reelle Zahlen">reellen Zahlen</a> enthalten in ihrer natürlichen Anordnung jeweils unendliche absteigende Ketten und sind somit nicht fundiert.

Die <a href="Potenzmenge" title="Potenzmenge">Potenzmenge</a> einer Menge mit der Teilmengenbeziehung als Ordnung ist genau dann fundiert, wenn die Menge <a href="Endliche_Menge" title="Endliche Menge">endlich</a> ist. Alle endlichen halbgeordneten Mengen sind fundiert, weil endliche Mengen nur endliche Ketten haben können.

Die folgenden Mengen sind fundiert, aber nicht totalgeordnet:

<ul><li>die <a href="Nat%C3%BCrliche_Zahl" title="Natürliche Zahl">natürlichen Zahlen</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {N} =\left\{1,2,3,\ldots \right\}}">

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {N} =\left\{1,2,3,\ldots \right\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d8aca16e799ecf0c96cafc7df9cdc056e23fb2e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.414ex; height:2.843ex;" alt="{\displaystyle \mathbb {N} =\left\{1,2,3,\ldots \right\}}" loading="lazy"> mit der Ordnung</li></ul>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\leq b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/41558abc50886fdf38817495b243958d7b3dd39b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.326ex; height:2.343ex;" alt="{\displaystyle a\leq b}" loading="lazy"> genau dann, wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> ein Teiler von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> ist</dd></dl></dd></dl>

<ul><li>die Menge der Untermoduln eines <a href="Noetherscher_Modul" class="mw-redirect" title="Noetherscher Modul">noetherschern Moduls</a> mit der Ordnung</li></ul>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M\leq N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e49d1bd89c5a14156a19cc822cd6837e74e06573.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.604ex; height:2.343ex;" alt="{\displaystyle M\leq N}" loading="lazy"> genau dann, wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N\subseteq M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N\subseteq M}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cfe9ab1adee54a74e4a9595b31e0f3302b9e4c2e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.604ex; height:2.343ex;" alt="{\displaystyle N\subseteq M}" loading="lazy"></dd></dl></dd></dl>

<ul><li>die Menge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {N} \times \mathbb {N} }">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {N} \times \mathbb {N} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5b25f8c4219e47350185be7ebdc5250c8d59ab35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.197ex; height:2.176ex;" alt="{\displaystyle \mathbb {N} \times \mathbb {N} }" loading="lazy"> aller Paare natürlicher Zahlen mit der Ordnung</li></ul>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (m,n)\leq (a,b)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a2189a1106b430dbe327882c1566a6ef47160396.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.447ex; height:2.843ex;" alt="{\displaystyle (m,n)\leq (a,b)}" loading="lazy"> genau dann, wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\leq a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\leq a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/02901ae019ed6bbaa674749a6d0ad036c96319e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.369ex; height:2.176ex;" alt="{\displaystyle m\leq a}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\leq b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\leq b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/032d1ff0c86d78316178e356fe77ff537fe0738b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.491ex; height:2.343ex;" alt="{\displaystyle n\leq b}" loading="lazy"></dd></dl></dd></dl>

<ul><li>die Menge der endlichen <a href="Wort_(Theoretische_Informatik)" class="mw-redirect" title="Wort (Theoretische Informatik)">Wörter</a> über einem vorgegebenen <a href="Alphabet_(Informatik)" title="Alphabet (Informatik)">Alphabet</a> mit der Ordnung</li></ul>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s\leq t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c12f663b9eb8759c0da898cc542d7cb3bcf5e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.029ex; height:2.176ex;" alt="{\displaystyle s\leq t}" loading="lazy"> genau dann, wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> eine Teilzeichenkette von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> ist</dd></dl></dd></dl>

<ul><li>die Menge der <a href="Regul%C3%A4rer_Ausdruck" title="Regulärer Ausdruck">regulären Ausdrücke</a> über einem vorgegebenen Alphabet mit der Ordnung</li></ul>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s\leq t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c12f663b9eb8759c0da898cc542d7cb3bcf5e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.029ex; height:2.176ex;" alt="{\displaystyle s\leq t}" loading="lazy"> genau dann, wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> ein Teilausdruck von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> ist</dd></dl></dd></dl>

<ul><li>jede Menge von Mengen mit der Ordnung</li></ul>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\leq B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8b9a5b16c80e28e48322cb621b6c445cb68fcaf2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.606ex; height:2.343ex;" alt="{\displaystyle A\leq B}" loading="lazy"> genau dann, wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> ist ein Element von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> (wirklich Element, nicht Teilmenge!)</dd></dl></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Länge_absteigender_Ketten">Länge absteigender Ketten</h2></div>

Ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (X,\leq )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (X,\leq )}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/05986ce35d21b64f59206cb040c9c1607dae82b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.631ex; height:2.843ex;" alt="{\displaystyle (X,\leq )}" loading="lazy"> eine fundierte Menge und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in X}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3e580967f68f36743e894aa7944f032dda6ea01d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.15ex; height:2.176ex;" alt="{\displaystyle x\in X}" loading="lazy">, dann sind die bei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> beginnenden absteigenden Ketten allesamt endlich, aber ihre Länge muss nicht beschränkt sein. Betrachte z. B. die Menge

<dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X:=\left\{(a,b)\in \mathbb {N} _{0}\times \mathbb {N} _{0}\mid a\geq b>0\vee a=b=0\right\}}">

<mrow>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X:=\left\{(a,b)\in \mathbb {N} _{0}\times \mathbb {N} _{0}\mid a\geq b>0\vee a=b=0\right\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/41040b7f549b964a575c00b13f078732e5b225aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:47.96ex; height:2.843ex;" alt="{\displaystyle X:=\left\{(a,b)\in \mathbb {N} _{0}\times \mathbb {N} _{0}\mid a\geq b>0\vee a=b=0\right\}}" loading="lazy"></dd></dl>

(wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {N} _{0}=\left\{0,1,2,3,\ldots \right\}}">

<msub>

</mrow>

</mrow>

</msub>

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {N} _{0}=\left\{0,1,2,3,\ldots \right\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7fd4d50fa72ddf6316ce71b4d2d15c1d3c4ea075.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.665ex; height:2.843ex;" alt="{\displaystyle \mathbb {N} _{0}=\left\{0,1,2,3,\ldots \right\}}" loading="lazy">) mit der Ordnung

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (m,n)\leq (a,b)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a2189a1106b430dbe327882c1566a6ef47160396.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.447ex; height:2.843ex;" alt="{\displaystyle (m,n)\leq (a,b)}" loading="lazy"> genau dann, wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a,b)=(0,0)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a,b)=(0,0)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8db5a957bc8ff8f9a17bc2fa2edab1f609a58d03.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.337ex; height:2.843ex;" alt="{\displaystyle (a,b)=(0,0)}" loading="lazy"> oder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=a\wedge n\geq b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=a\wedge n\geq b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3f2f61dfeefe3da1107605408a1914193d807f4b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:14.442ex; height:2.343ex;" alt="{\displaystyle m=a\wedge n\geq b}" loading="lazy"></dd></dl>

Darin sind z. B. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (0,0)>(4,1)>(4,2)>(4,3)>(4,4)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (0,0)>(4,1)>(4,2)>(4,3)>(4,4)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/aca6517f40dc3f7df41d97a73dc596f84d085542.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:38.235ex; height:2.843ex;" alt="{\displaystyle (0,0)>(4,1)>(4,2)>(4,3)>(4,4)}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (0,0)>(2,1)>(2,2)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (0,0)>(2,1)>(2,2)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c68329425874df4583e022c4f6f800325dd5bdf7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.701ex; height:2.843ex;" alt="{\displaystyle (0,0)>(2,1)>(2,2)}" loading="lazy">. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> ist fundiert, aber es gibt bei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (0,0)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (0,0)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5d630d3e781a53b0a3559ae7e5b45f9479a3141a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (0,0)}" loading="lazy"> beginnende absteigende Ketten beliebiger (endlicher) Länge.

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Strukturelle_Induktion" title="Strukturelle Induktion">Strukturelle Induktion</a></li>

<li><a href="Wohlfundierte_Relation" title="Wohlfundierte Relation">Wohlfundierte Relation</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> Wolfgang Wechler: <cite style="font-style:italic">Universal Algebra for Computer Scientists</cite>. Springer-Verlag, Berlin 1992, ISBN 3-540-54280-9, S. 35–39.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Fundierte+Menge&rft.au=Wolfgang+Wechler&rft.btitle=Universal+Algebra+for+Computer+Scientists&rft.date=1992&rft.genre=book&rft.isbn=3540542809&rft.pages=35-39&rft.place=Berlin&rft.pub=Springer-Verlag" style="display:none">

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-05-15" href="https://de.wikipedia.org/wiki/?title=Fundierte_Menge&oldid=256031623">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>